import java.util.*;

/**
 * @author LKQ
 * @date 2021/12/12 9:07
 * @description 利用滑动窗口解决问题
 */
public class Solution {
    public static void main(String[] args) {
        String s = "wordgoodgoodgoodbestword";
        String[] words = {"word","good","good", "best"};
        Solution solution = new Solution();
        solution.findSubstring(s, words);
    }

    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> ans = new ArrayList<>();
        Count count = new Count();
        // 字符串长度n, 数组单词个数, 右指针位置
        int n = s.length(), m = words.length, rk = 0 ;
        for (int i = 0; i < m; i++) {
            count.add(words[i], 1);
        }
        // words长度 >= 1.,且每个单词长度相同，
        int wordsLength = words[0].length();
        Count changeCount;
        for (int i = 0; i <= n - m * wordsLength;) {
            rk = i;
            changeCount = (Count) count.clone();
            int hit = 0, wordSum = m;
            while (wordSum != 0){
                String temp = s.substring(i, i + wordsLength);
                if (!changeCount.containsKey(temp) || changeCount.get(temp) <= 0) {
                    break;
                }else {
                    changeCount.add(temp, -1);
                    hit++;
                }
                wordSum--;
                i += wordsLength;
            }
            if (hit == m) {
                ans.add(rk);
            }
            i = rk + 1;
            if (!count.containsKey(s.substring(i, i + wordsLength))) {
                i = rk + wordsLength;
            }
        }
        return ans;
    }
}

class Count extends HashMap<String, Integer> {
    public int get(String s) {
        return containsKey(s) ? super.get(s) : 0;
    }

    public void add(String k, int v) {
        put(k, get(k) + v);
    }
}
